K

K-近邻 (K-Nearest Neighbor) 算法,也叫 K 最近邻算法，1968年由 Cover 和 Hart 提出，是机器学习算法中比较成熟的算法之一。K-近邻算法使用的模型实际上对应于对特征空间的划分。KNN 算法不仅可以用于分类，还可以用于回归。

K-近邻算法就是，先给定一个训练数据集，这个数据集中可能是某类物品的特征及分类，然后给出某个物品的特征，根据训练数据集中的各个物品的特征与这个需要判别分类的物品的“距离”远近，找出距离最近的 k 个，然后这 k 个物品中最多物品所归属的那个分类就是这个需要判别的物品所归属分类判断的结果。

注：一般训练集和测试集都是 7:3 或者 8:2，或者 7.5:2.5。

海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：

海伦收集约会数据巳经有了一段时间，她把这些数据存放在文本文件 datingTestSet.txt 中，每个样本数据占据一行，总共有 1000 行。海伦的样本主要包含以下 3 种特征：

注：datingTestSet.txt 数据集及整个算法的完整实现都在我的仓库中

https://gitcode.net/weixin_52185996/knn

所给数据集中包含分类的特征和分类标签两种算法所需的类型，为了方便计算我们将其分开并格式化为我们需要的数据格式，分别存入两个 NumPy 矩阵中：

这里我们使用 Matplotlib 库来创建散点图

上述散点图表示 datingDataMat 矩阵的第二和第三列数据，横轴表示“玩视频游戏所耗时间百分比”，纵轴表示“每周消费的冰淇淋公升数”。不同的颜色就表示三个不同的类别。

如果利用欧式距离来计算样本之间的差异的话则有：

\qquad\qquad\qquad\qquad\qquad distance = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}

如果 x 表示”每年获得的飞行常客里程数“、y 表示“玩视频游戏所耗时间百分比”、z 表示“每周消费的冰淇淋公升数”的话，显然同一样本的不同特征值之间的差异实在太大，比如说飞行常客的里程数对结果的影响是在太大了，因为它的数值远远大于了其他两个特征；但对海伦来说这三种特征是同样重要的，所以就需要对这三种特征分别进行归一化：

\qquad\qquad\qquad\qquad\qquad\qquad\qquad newValue=\frac{(oldValue-min)}{(max-min)}

其中的 min 和 max 分别是对应的特征集中的最小和最大值。

每列的最小值放在 minVals 中，每列的最大值放在 maxVals 中，函数返回的 ranges 和 minVals 都是为了方便算法测试才返回的，也可以选择不返回。

在这里我们用 10% 数据集中的数据来进行测试，90% 的数据用作训练输入，因为这个数据集本身就是随机排列的，所以我们为了方便可以直接去数据集的前 10% 用作测试集，后 90% 用作训练集。

文件 knn_study 中的 KNN 算法关键实现

这里的 knn_study.py 中的 classify0 方法就是用来计算样本之间的距离，给出算法结果的，是算法的关键部分。

使用简单的命令来看看算法的实际运行效果